package algorithm7.leetcode.每日一题.YEAR2023.month5;

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author: permission
 * @Date: 2023/5/14 16:26
 * @Version: 1.0
 * @ClassName: DAY20230514_LC1054
 * @Description: 1054. 距离相等的条形码
 */
public class DAY20230514_LC1054 {

    /*

    在一个仓库里，有一排条形码，其中第 i 个条形码 barcodes[i]。
    请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。


    示例 1：
    输入：barcodes = [1,1,1,2,2,2]
    输出：[2,1,2,1,2,1]

    示例 2：
    输入：barcodes = [1,1,1,1,2,2,3,3]
    输出：[1,3,1,3,2,1,2,1]


     */
    public int[] rearrangeBarcodes(int[] barcodes) {
//        return handle1(barcodes);
        return handle2(barcodes);
    }

    /*
        方法二：
            全排列，重新排列后遍历每个位置 i != i-1 即满足
            (LC超时。。。)
     */
    private int[] handle2(int[] barcodes) {
        ArrayList<Integer> list = (ArrayList<Integer>) Arrays.stream(barcodes).boxed().collect(Collectors.toList());
        Set<ArrayList<Integer>> fullPermutation = new HashSet<>(16);
        getFullPermutation(list, 0, fullPermutation);
        int[] res = new int[barcodes.length];
        for (ArrayList<Integer> arrayList : fullPermutation) {
            res[0] = arrayList.get(0);
            for (int i = 1; i < arrayList.size(); i++) {
                if (arrayList.get(i) == arrayList.get(i - 1)) {
                    break;
                }
                res[i] = arrayList.get(i);
                if (i == barcodes.length - 1) {
                    return res;
                }
            }
        }
        return res;
    }

    private void getFullPermutation(ArrayList<Integer> list, int index, Set<ArrayList<Integer>> fullPermutation) {
        if (index == list.size()) {
            fullPermutation.add((ArrayList<Integer>) list.clone());
            return;
        }
        for (int i = index; i < list.size(); i++) {
            Collections.swap(list, index, i);
            getFullPermutation(list, index + 1, fullPermutation);
            Collections.swap(list, i, index);
        }
    }
    /*
        大根堆，先取出现次数最多的，再取第二多的，依次间隔取
     */
    private int[] handle1(int[] barcodes) {
        int len = barcodes.length;
        Map<Integer, Integer> map = new HashMap<>(16);
        // 优先级队列 0为key， 1为出现的次数， 按次数排序
        PriorityQueue<int[]> queue = new PriorityQueue<>(((o1, o2) -> o2[1] - o1[1]));
        // 统计条码出现的次数
        for (int barcode : barcodes) {
            map.put(barcode, map.getOrDefault(barcode, 0) + 1);
        }
        // 插入大根堆
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.offer(new int[]{entry.getKey(), entry.getValue()});
        }
        int[] res = new int[len];
        // 取堆顶，如果上一次也是取得这个条码，再取出一个（第二个），使用后次数减1。 判断剩余次数是否大于0，大于0放回大根堆
        for (int i = 0; i < len; i++) {
            int[] head = queue.poll();
            int barcode = head[0];
            int count = head[1];
            if (i != 0 && barcode == res[i - 1]) {
                // 因为题目保证肯定有解，queue里面的都是唯一的key，所以第二次取出的肯定符合要求
                int[] head2 = queue.poll();
                int barcode2 = head2[0];
                int count2 = head2[1];
                res[i] = barcode2;
                if (count2 > 1) {
                    queue.offer(new int[]{barcode2, --count2});
                }
                // 放回
                queue.offer(head);
                continue;
            }
            res[i] = barcode;
            if (count > 1) {
                queue.offer(new int[]{barcode, --count});
            }
        }
        return res;
    }

    @Test
    void t1() {
        int[] barcodes = {4,4,4,4,3,3,7,3,7,3};
        long start = System.currentTimeMillis();
        int[] res = rearrangeBarcodes(barcodes);
        long end = System.currentTimeMillis();
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i] + " ");
        }
        System.out.println();
        System.out.println("(end - start) = " + (end - start));
    }
}
